package com.da.javatest.niuke.baodian;

/**
 * @author chenlida
 * @date 2020/10/12 14:49
 * https://www.nowcoder.com/practice/3c2451031d024387a0f44dcab77a8abc?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C57Stack {
    public static int getHeight(int[] men, int n) {
        int[] result = new int[n];
        //辅助数组，用来记录有多少个元素比当前元素小，累计自身的，所以初始值为1
        result[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            result[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (men[j] < men[i] && result[j] + 1 > result[i]) {
                    result[i] = result[j] + 1;
                }
                max = Math.max(max, result[i]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(getHeight(new int[] {1, 6, 2, 5, 3, 4}, 6));
    }
}
